The present invention relates to adaptive computing stystems and more particularly to such systems which employ a data structure providing a multiplicity of so-called classifiers.
Classifier computing systems represent attempts to enable computers to perform inductive logic. Such systems are described in the context of inductive logic generally in a treatise entitled "Induction" written by John H. Holland et al. and published in 1986 by the MIT Press, Cambridge, Massachusetts. U.S. Pat. No. 4,697,242 entitled Adaptive Computing System Capable of Learning and Discovery was issued to John H. Holland and Arthur W. Burks on Sept. 29, 1987 and relates to a classifier-type computing system.
In general, classifier-type computing systems are set up to respond to a binary encoded input signal, typically comprising a succession of messages. It is the function of the classifier system to generate appropriate responses to the messages. In order for the classifier system to evolve or adapt, the environment or source must also provide a reinforcement signal, i.e. a reward, for good or appropriate responses.
As described by Holland as well as others in the field, the basic data structure of a classifier includes a match string, a response message or response message definer, and a strength value associated with the classifier. The match string is typically encoded in a ternary format in which each character may be a "1", a "0" (zero) or a "#". The "#" character designates a "don't care" condition. In the system described in the '242 patent, messages from both the environment and from classifiers are posted to a message list where, on sucessive cycles, they may be examined and attempted to be matched by the various classifiers.
In the Holland classifier system, as well as in most other classifier systems proposed heretofore, the match which must be obtained between a given match string and a posted message must be relatively exact. The only tolerance of which the system is capable is provided through the use of the ternary encoding system for the match string where a particular character may be given a don't care (#) value.
Depending on the type of problem which the classifier system is intended to deal with, reward or reinforcement may be either immediate or intermittent. Immediate reinforcement is, for example, appropriate where a solution to a Boolean problem is being sought. A system providing such immediate reinforcement is described in a paper by Stewart W. Wilson entitled "Classifier System Learning of A Boolean Function" RIS 27 r, The Rowland Institute For Science, Cambridge, MA, Feb. 9, 1986. The Holland classifier system on the other hand contemplates that reinforcement will be intermittent and must be distributed amongst a succession of classifiers which contributed to the rewarded end result. The '242 patent describes a "bucket brigade" algorithm for building the strength value of classifiers based upon their being active at the time of reinforcement. In addition, the data structure for the classifiers may include a tag which identifies the predecessor of a classifier contributing to the rewarded response.
In addition to rewarding useful classifiers, adaptive computing systems of this type also contemplate the periodic application of various genetic operators so that new classifiers will evolve. The genetic algorithms are applied to classifiers selected from the overall population of classifiers with a likelihood or statistical chance of selection based upon the strength of the classifier. By using a likelihood or stochastic selection process, a useful diversity is maintained in the population of classifiers. Among the known genetic operators typically applied to generate new classifiers from selected classifiers are a form of "mutation" in which random bits of the match string are altered in state. A second very important form of genetic operator is called "crossover" in which a pair of classifiers ("parents") are combined by splitting the match strings of both parent classifiers at a random position and exchanging parts to form two new "child" classifiers. Typically, the ("parents") are left in the population and the new classifiers ("children") replace classifiers which are deleted with a likelihood based on their having low strength values.
As indicated previously, most classifier systems disclosed heretofore are relatively intolerant with respect to determining whether a match exists. In systems in which the input may be somewhat noisy or subject to variation, this intolerance leads to a so-called "brittleness" which can lead to failure or anomalous results. A paper by Lashon B. Booker entitiled "Improving The Performance of Genetic Algorithms In Classifier Systems" Proc. Intern. Conf. on Gen. Alg. and Their Appl., Pittsburgh, PA, July 1985, 80-92 proposed two alternate methods of scoring the match to make the system somewhat more tolerant. In one approach, he proposed a match score, designated M3, which measured the Hamming distance between a message and a match string (called a "taxon"). The basic data structure of the classifier, however, was left unchanged.
In accordance with the present invention, the data structure of the classifier system is modified to include a weighting value for each bit in the match string. As each match string is compared with a posted message, a score value is generated by summing the weights associated with the matched bits. Thus, the system can accommodate messages in which the relative importance of various bits differ within the message. This is believed to be more in line with the problems encountered in real life situations. Further, by applying genetic operations to the weighting values as well as to the match string itself, the performance of successive evolutions of classifiers may be improved.